package demo;

import java.util.TreeMap;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //等价多米诺骨牌对的数量
    public int numEquivDominoPairs(int[][] dominoes) {
        int ans=0;
        int[]map=new int[101];
        for(int[]i:dominoes) {
            int x=i[0],y=i[1];
            if(x>y) {
                x^=y;
                y^=x;
                x^=y;
            }
            int t=x*10+y;
            ans+=map[t]++;
        }
        return ans;
    }

    //奇偶跳
    public int oddEvenJumps(int[] arr) {
        //动态规划 + 红黑树
        int len = arr.length;
        //记录三种状态 2 偶数好索引 1 奇数好索引 0 坏索引 3 奇和偶好索引;
        byte[] dp = new byte[len];
        TreeMap<Integer,Integer> map = new TreeMap<>();
        dp[len-1] = 3;
        map.put(arr[len-1],len-1);
        int sum = 1;
        for(int i=len-2; i>=0; i--){
            Integer j;
            if((j = map.ceilingKey(arr[i])) != null && dp[map.get(j)] >= 2){
                dp[i] = 1;
                sum++;
            }
            if((j = map.floorKey(arr[i])) != null &&
                    ((j = map.get(j)) == len-1 || dp[j] == 1 || dp[j] == 3)) dp[i] += 2;
            map.put(arr[i],i);
        }
        return sum;
    }
}
